This invention relates to image processing.
Image compression techniques such as MPEG (moving pictures experts group) use motion estimation in coding images. As shown in FIG. 1, motion estimation approximates the pixels in a current frame 10 of a video or graphics image based on the pixels in a previous frame 12. Specifically, motion estimation using block matching algorithms can take advantage of the temporal redundancy between successive frames of video or graphics images. Block matching algorithms search a region of an image frame called a search window 18 to determine the movement of a portion of an image such as a leaf 13 that is within a current block of pixels 14 from one frame 12 to the next 10. The search window 18 typically includes the pixels in the previous frame 12 that surround the location that corresponds to the location of the current block of pixels 14 in the current frame 10 because these surrounding pixels are more likely than other pixels in the previous frame 12 to include a matching block of pixels 15 for the current block of pixels 14. A motion vector 16 represents the direction and amount of movement of the matching block of pixels 15 from the previous frame 12 and in that way implies the direction and amount of motion that will occur between the previous frame 12 and the current frame 10. Here the motion vector 16 shows that the matching block of pixels 15 is in an area above and to the right of the location corresponding to the location of the current block of pixels 14 in the current image 10, indicating that the leaf 13 is falling down and to the left. In this way, less storage space and bandwidth are used in transmitting a given pixel block because only the motion vector for the pixel block need be transmitted rather than the pixel block itself.
FIG. 2 shows that when the search windows 20a-b for different pixel blocks 22a-b overlap, block matching algorithms read some pixels more than once, such as the pixels in the shaded region.